/*
 * =====================================================================================
 *
 *       Filename:  limingle.c
 *
 *    Description:  Implement a Queue with two Stacks, one Stack used for pushing and
 *    the other used for poping.
 *
 *        Created:  2020-07-02 16:26
 *
 *         Author:  limingle
 *          Email:  lml@xdja.com
 *   Organization:  XDJA Tech.CO.ltd.
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node, List;

typedef struct {
    List *top;
    size_t count;
} Stack;

Stack *StackCreate()
{
    return (Stack *)calloc(1, sizeof(Stack));
}

void StackPush(Stack * stack, int data)
{
    if (NULL != stack) {
        Node *new_node = (Node *)calloc(1, sizeof(Node));
        new_node->data = data;
        new_node->next = stack->top;
        stack->top = new_node;
        stack->count = stack->count + 1;
    }
}

int StackPeek(Stack * stack)
{
    int result = -1;

    if (NULL != stack && NULL != stack->top) {
        result = stack->top->data;
    }

    return result;
}

int StackPop(Stack * stack)
{
    int result = -1;

    do {
        if (NULL == stack || NULL == stack->top) {
            break;
        }
        Node *top = stack->top;
        stack->top = top->next;
        result = top->data;
        free(top);
        stack->count = stack->count - 1;
    }
    while (false);

    return result;
}

size_t StackSize(Stack * stack)
{
    size_t size = 0;
    do {
        if (NULL == stack) {
            break;
        }
        size = stack->count;
    }
    while (false);
    return size;
}

bool StackIsEmpty(Stack * stack)
{
    return (NULL == stack) || (NULL == stack->top);
}

void StackFree(Stack * stack)
{
    if (NULL != stack) {
        while (NULL != stack->top) {
            StackPop(stack);
        }
        free(stack);
    }
}

typedef struct {
    Stack *pushStack;
    Stack *popStack;
} MyQueue;

/** Initialize your data structure here. */
MyQueue *myQueueCreate()
{
    MyQueue *queue = (MyQueue *)calloc(1, sizeof(MyQueue));
    queue->pushStack = StackCreate();
    queue->popStack = StackCreate();
    return queue;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue * obj, int x)
{
    if (NULL != obj) {
        StackPush(obj->pushStack, x);
    }
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue * obj)
{
    int result = -1;
    do {
        if (NULL == obj) {
            break;
        }

        if (!StackIsEmpty(obj->popStack)) {
            result = StackPop(obj->popStack);
            break;
        }

        if (StackIsEmpty(obj->pushStack)) {
            break;
        }

        while (!StackIsEmpty(obj->pushStack)) {
            StackPush(obj->popStack, StackPop(obj->pushStack));
        }

        result = StackPop(obj->popStack);
    }
    while (false);

    return result;
}

/** Get the front element. */
int myQueuePeek(MyQueue * obj)
{
    int result = -1;
    do {
        if (NULL == obj) {
            break;
        }

        if (!StackIsEmpty(obj->popStack)) {
            result = StackPeek(obj->popStack);
            break;
        }

        if (StackIsEmpty(obj->pushStack)) {
            break;
        }

        while (!StackIsEmpty(obj->pushStack)) {
            StackPush(obj->popStack, StackPop(obj->pushStack));
        }

        result = StackPeek(obj->popStack);
    }
    while (false);

    return result;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue * obj)
{
    if (NULL == obj || NULL == obj->pushStack || NULL == obj->popStack) {
        return true;
    } else {
        return StackIsEmpty(obj->popStack)
            && StackIsEmpty(obj->pushStack);
    }
}

void myQueueFree(MyQueue * obj)
{
    if (obj != NULL) {
        StackFree(obj->pushStack);
        StackFree(obj->popStack);
        free(obj);
    }
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
 */
int main(int argc, const char *argv[])
{
    MyQueue *obj = myQueueCreate();
    myQueuePush(obj, 1);
    myQueuePush(obj, 2);
    myQueuePush(obj, 3);
    int p1 = myQueuePeek(obj);
    int p2 = myQueuePop(obj);
    int p3 = myQueuePop(obj);

    printf("%d %d %d\n", p1, p2, p3);

    if (myQueueEmpty(obj)) {
        printf("empty.\n");
    } else {
        printf("not empty.\n");
    }

    int p4 = myQueuePop(obj);
    printf("%d\n", p4);

    if (myQueueEmpty(obj)) {
        printf("empty.\n");
    } else {
        printf("not empty.\n");
    }

    myQueueFree(obj);

    return 0;
}
